package com.topcoder.srm516;

import java.util.HashMap;
import java.util.HashSet;

public class NetworkXMessageRecovery {
	public String recover2(String[] messages) {
		boolean[][] g = new boolean[128][128];
		int[] parent = new int[128];
		boolean[] exist = new boolean[128];
		int len = 0;
		
		for (String message : messages) {
			char[] c = message.toCharArray();
			for (int i=0; i<c.length; i++) {
				if (!exist[c[i]]) {
					exist[c[i]] = true;
					len++;
				}
				if (i>0 && !g[c[i-1]][c[i]]) {
					g[c[i-1]][c[i]]= true;
					parent[c[i]]++;
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for (int i=0; i<len; i++) {
			for (char c='A'; c<='z'; c++) {
				if (exist[c] && parent[c] == 0) {
					exist[c] = false;
					sb.append(c);
					for (int j='A'; j<='z'; j++) {
						if (g[c][j]) {
							g[c][j] = false;
							parent[j]--;
						}
					}
					break;
				}
			}
		}
		
		return sb.toString();
	}
	
	// ------------------------------------------------------------------------
	// Another implementation
	// ------------------------------------------------------------------------
	
	private HashMap<Character, Node> map;
	
	public String recover(String[] messages) {
		map = new HashMap<Character, Node>();
		for (String message : messages) {
			char[] c = message.toCharArray();
			for (int i=0; i<c.length; i++) {
				if (i>0) getNode(c[i-1]).children.add(c[i]);
				getNode(c[i]);
			}
		}
		
		for (char c : map.keySet()) {
			for (char child : map.get(c).children) {
				getNode(child).parentCount++;
			}
		}
		
		StringBuilder res = new StringBuilder();
		while (!map.isEmpty()) {
			char min = (char)('z' + 1);
			for (Node node : map.values()) {
				if (node.parentCount == 0 && node.c < min) {
					min = node.c;
				}
			}
			
			res.append(min);
			for (char child : map.get(min).children) {
				map.get(child).parentCount--;
			}
			map.remove(min);
		}
		
		return res.toString();
	}
	
	private Node getNode(char c) {
		if (!map.containsKey(c)) {
			map.put(c, new Node(c));
		}
		return map.get(c);
	}
	
	private class Node {
		HashSet<Character>	children;
		int 				parentCount;
		char 				c;
		public Node(char c) {
			this.c = c;
			children = new HashSet<Character>();
		}
	}
}
